/*
最小生成树————Kruskal算法+并查集算法
*/
class DisjointSetUnion {//并查集类
private:
    vector<int> f, rank;
    int n;
public:
    DisjointSetUnion(int _n) {//类的构造函数
        n = _n;
        rank.resize(n, 1);
        f.resize(n);
        for (int i = 0; i < n; i++) {
            f[i] = i;
        }
    }

    int find(int x) {//并查集中查找连通分量队长
        return f[x] == x ? x : f[x] = find(f[x]);
    }

    int unionSet(int x, int y) {//合并两个连通分量
        int fx = find(x), fy = find(y);
        if (fx == fy) {
            return false;
        }
        if (rank[fx] < rank[fy]) {
            swap(fx, fy);
        }
        rank[fx] += rank[fy];
        f[fy] = fx;
        return true;
    }
};

struct Edge {
    int len, x, y;
    Edge(int len, int x, int y) : len(len), x(x), y(y) {
    }
};

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        auto dist = [&](int x, int y) -> int {//计算距离
        /*auto的原理就是根据后面的值，来自己推测前面的类型是什么。*/
            return abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1]);
        };
        int n = points.size();
        DisjointSetUnion dsu(n);//初始化并查集
        vector<Edge> edges;//构造图需要的边集
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                edges.emplace_back(dist(i, j), i, j);
            }
        }
        sort(edges.begin(), edges.end(), [](Edge a, Edge b) -> int { return a.len < b.len; });//将边按照从小到大进行排序
        int ret = 0, num = 1;//ret计算累计权重和，num记录生成树中的顶点个数
        for (auto& [len, x, y] : edges) {//遍历边集合
            if (dsu.unionSet(x, y)) {//如果两个顶点属于不同的连通分量，选择该边
                ret += len;
                num++;
                if (num == n) {//循环终止条件：生成树顶点已经不能再增加
                    break;
                }
            }
        }
        return ret;
    }
};

